\documentclass[a4paper,UKenglish]{lipics}
  %for A4 paper format use option "a4paper", for US-letter use option "letterpaper"
  %for british hyphenation rules use option "UKenglish", for american hyphenation rules use option "USenglish"
 % for section-numbered lemmas etc., use "numberwithinsect"
 
\usepackage{microtype}%if unwanted, comment out or use option "draft"
%\usepackage{amsthm,amssymb}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage{algorithmic,algorithm}

\input{macros-stacs}
%\graphicspath{{./graphics/}}%helpful if your graphic files are in another directory

\bibliographystyle{plain}% the recommended bibstyle

% Author macros %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{Information Spreading in Dynamic Networks \footnote{This work  supported in part by the following grants: Nanyang Technological University grant M58110000 , Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 2 grant MOE2010-T2-2-082,
US NSF grants CCF-1023166 and CNS-0915985, and a grant from the US-Israel Binational Science
Foundation (BSF).}}
%\titlerunning{A Sample LIPIcs Article} %optional, in case that the title is too long; the running title should fit into the top page column

\author[1]{Chinmoy Dutta}
\author[2]{Gopal Pandurangan}
\author[1]{Rajmohan Rajaraman}
\author[1]{Zhifeng Sun}
\affil[1]{College of Computer and Information Science, \\
  Northeastern University \\
  Boston, MA 02115, USA \\
  \texttt{\tt \{chinmoy,rraj,austin\}@ccs.neu.edu}}
\affil[2]{Division of Mathematical Sciences \\
  Nanyang Technological University \\
  Singapore 637371    \\ and \\
  Department of Computer Science \\
  Brown University \\
  Providence RI 02912, USA \\
  \texttt{gopalpandurangan@gmail.com}}
%\authorrunning{} 
%optional. First: Use abbreviated first/middle names. Second (only in severe cases): Use first author plus 'et. al.'

\Copyright[nc-nd] %choose "nd" or "nc-nd"
          {C. Dutta, G. Pandurangan, R. Rajaraman and Z. Sun}

\subjclass{F.2  [ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY]:
Non-numerical Algorithms and Problems---computations on discrete
structures; G.2.2 [Discrete Mathematics]: Graph Theory---graph algorithms
G.2.2 [Discrete Mathematics]: Graph Theory---network problems; C.2.4 [COMPUTER COMMUNICATION
NETWORKS]: Distributed Systems } 
%mandatory: Please choose ACM 1998 classifications from 
%http://www.acm.org/about/class/ccs98-html . E.g., cite as "F.1.1 Models of Computation". 

\keywords{Dynamic networks, Distributed Computation, Information Spreading, Gossip, Lower Bounds}
% mandatory: Please provide 1-5 keywords
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%Editor-only macros (do not touch as author)%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\serieslogo{}%please provide filename (without suffix)
\volumeinfo%(easychair interface)
  {Billy Editor, Bill Editors}% editors
  {2}% number of editors: 1, 2, ....
  {Conference title on which this volume is based on}% event
  {1}% volume
  {1}% issue
  {1}% starting page number
\EventShortName{}
\DOI{10.4230/LIPIcs.xxx.yyy.p}% to be completed by the volume editor
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\maketitle

\begin{abstract}
We study the fundamental problem of information spreading (also known
as gossip) in dynamic networks.  In gossip, or more generally,
$k$-gossip, there are $k$ pieces of information (or tokens) that are
initially present in some nodes and the problem is to disseminate the
$k$ tokens to all nodes.  The goal is to accomplish the task in as few
rounds of distributed computation as possible.  The problem is
especially challenging in dynamic networks where the network topology
can change from round to round and can be controlled by an on-line
adversary.

The focus of this paper is on the power of token-forwarding
algorithms, which do not manipulate tokens in any way other than
storing and forwarding them.  We first consider a worst-case
adversarial model first studied by Kuhn, Lynch, and
Oshman~\cite{kuhn+lo:dynamic} in which the communication links for
each round are chosen by an adversary, and nodes do not know who their
neighbors for the current round are before they broadcast their
messages. \junk{The model allows the study of the fundamental
  computation power of dynamic networks.}Our main result is an
$\Omega(nk/\log n)$ lower bound on the number of rounds needed for any
deterministic token-forwarding algorithm to solve $k$-gossip.  This
resolves an open problem raised in~\cite{kuhn+lo:dynamic}, improving
their lower bound of $\Omega(n \log k)$, and matching their upper
bound of $O(nk)$ to within a logarithmic factor.

\junk{Our main result is an almost tight lower bound on the number of
  rounds needed to perform gossip which also answers an open question
  raised in Kuhn et al. [STOC 2010], who also show a $O(nk)$ round
  distributed algorithm.  Thus our bound is tight to within a
  logarithmic factor and almost closes the gap between the upper and
  lower bounds shown in Kuhn et al. paper.}

Our result shows that one cannot obtain significantly efficient (i.e.,
subquadratic) token-forwarding algorithms for gossip in the
adversarial model of~\cite{kuhn+lo:dynamic}.  We next show that
token-forwarding algorithms can achieve subquadratic time in the
offline version of the problem, where the adversary has to commit all
the topology changes in advance at the beginning of the
computation. We present two polynomial-time offline token-forwarding
algorithms to solve $k$-gossip: (1) an $O(\min\{nk, n^{1.5}\sqrt{\log
  n}\})$ round algorithm, and (2) an $(O(n^\eps), \log n)$ bicriteria
approximation algorithm, for any $\eps > 0$, which means that if $L$
is the number of rounds needed by an optimal algorithm, then our
approximation algorithm will complete in $O(n^\eps L)$ rounds and the
number of tokens transmitted on any edge is $O(\log n)$ in each
round. Our results are a step towards understanding the power and
limitation of token-forwarding algorithms in dynamic networks.

\end{abstract}

\input{intro}
\input{pre}
\input{lowerbound}
\input{offline}
%\input{weak}
\input{open}

%%
%% Bibliography
%%
\bibliography{refs}
\input{appendix}
\end{document}
